package cn.yuemouren.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @Author: Timi
 * @Description: 438. 找到字符串中所有字母异位词
 * @Date: 2020/7/30 8:24
 */
public class Test_438 {

    public List<Integer> findAnagrams(String s, String p) {

        Map<Character,Integer> sMap = new HashMap<Character,Integer>();
        Map<Character, Integer> pMap = new HashMap<Character,Integer>();
        for (char c : p.toCharArray()){
            pMap.put(c,pMap.getOrDefault(c,0) + 1);
        }
        List<Integer> result = new ArrayList<>();
        int l = 0,r = 0,count = 0,pLeN = p.length();
        while ( r < s.length()){
            char c = s.charAt(r);
            sMap.put(c,sMap.getOrDefault(c,0) + 1);

            //如果 p 中包含当前字符，且s的窗口中该字符出现次数不足，则该字符可以作为候选字符，count加一
            if(pMap.containsKey(c) && sMap.get(c) <= pMap.get(c)){
                count++;
            }

            //如果count 等于 p的长度，证明出现字母异位词，将l存入到返回集合中
            if(count == pLeN){
                result.add(l);
            }

            //当窗口大小等于p长度时，窗口左边需要收缩一个字符
            while ((r - l + 1) == pLeN){
                char lc = s.charAt(l);
                //判断收缩字符是不是候选字符
                if(pMap.containsKey(lc) && sMap.get(lc) <= pMap.get(lc)){
                    count--;
                }
                sMap.put(lc,sMap.getOrDefault(lc,1) - 1);
                l++;
            }
            r++;
        }
        return result;
    }


}
